#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: longest_quence.py 
@version:
@time: 2023/12/24 
"""


def longest_sequence(s1, s2):
    len1 = len(s1)
    len2 = len(s2)

    array = [[0] * (len2 + 1) for _ in range(len1 + 1)]
    # 定义一个维度为len1xlen2的二维数组，初始化时，其元素均为0.

    for i in range(1, len1 + 1):
        for j in range(1, len2 + 1):
            # 逐行填充二维数组，利用双层循环，根据状态转移方程更新二维数组。
            # 由于array初始化时所有元素均为0，因此双层循环的i、j均从1开始即可

            # 状态转移方程如下
            if s1[i - 1] == s2[j - 1]:
                array[i][j] = array[i - 1][j - 1] + 1
            else:
                array[i][j] = max(array[i][j - 1], array[i - 1][j])

            """
            输入  空  B  D  C  A
            空    0  0  0  0  0
            A    0
            B    0    
            C    0
            D    0
            
            v
            
            输入  空  B  D  C  A
            空    0  0  0  0  0
            A    0  0  0  0  1
            B    0    
            C    0
            D    0
            
            v

            输入  空  B  D  C  A
            空    0  0  0  0  0
            A    0  0  0  0  1
            B    0  1  1  1  1  
            C    0
            D    0         
            
            v

            输入  空  B  D  C  A
            空    0  0  0  0  0
            A    0  0  0  0  1
            B    0  1  1  1  1  
            C    0  1  1  2  2 
            D    0         

            v

            输入  空  B  D  C  A
            空    0  0  0  0  0
            A    0  0  0  0  1
            B    0  1  1  1  1  
            C    0  1  1  2  2 
            D    0  1  1  2  2                      
            """
    return array[len1][len2]


print(longest_sequence('ABCB', 'BDCA'))
print(longest_sequence('ABC', 'ABC'))
print(longest_sequence('ABD', 'RTY'))
